home *** CD-ROM | disk | FTP | other *** search
/ Acorn RISC PD-CD 1 / Acorn RISC PD-CD 1.iso / utilities / _graphics / graphics / _jpeg / c / jwrgif < prev    next >
Encoding:
Text File  |  1991-10-28  |  14.3 KB  |  498 lines
  1. /*
  2.  * jwrgif.c
  3.  *
  4.  * Copyright (C) 1991, Thomas G. Lane.
  5.  * This file is part of the Independent JPEG Group's software.
  6.  * For conditions of distribution and use, see the accompanying README file.
  7.  *
  8.  * This file contains routines to write output images in GIF format.
  9.  *
  10.  * These routines may need modification for non-Unix environments or
  11.  * specialized applications.  As they stand, they assume output to
  12.  * an ordinary stdio stream.
  13.  *
  14.  * These routines are invoked via the methods put_pixel_rows, put_color_map,
  15.  * and output_init/term.
  16.  */
  17.  
  18. /*
  19.  * This code is loosely based on ppmtogif from the PBMPLUS distribution
  20.  * of Feb. 1991.  That file contains the following copyright notice:
  21.  *    Based on GIFENCODE by David Rowley <mgardi@watdscu.waterloo.edu>.
  22.  *    Lempel-Ziv compression based on "compress" by Spencer W. Thomas et al.
  23.  *    Copyright (C) 1989 by Jef Poskanzer.
  24.  *    Permission to use, copy, modify, and distribute this software and its
  25.  *    documentation for any purpose and without fee is hereby granted, provided
  26.  *    that the above copyright notice appear in all copies and that both that
  27.  *    copyright notice and this permission notice appear in supporting
  28.  *    documentation.  This software is provided "as is" without express or
  29.  *    implied warranty.
  30.  *
  31.  * We are also required to state that
  32.  *    "The Graphics Interchange Format(c) is the Copyright property of
  33.  *    CompuServe Incorporated. GIF(sm) is a Service Mark property of
  34.  *    CompuServe Incorporated."
  35.  */
  36.  
  37. #include "jinclude.h"
  38.  
  39. #ifdef GIF_SUPPORTED
  40.  
  41.  
  42. static decompress_info_ptr dcinfo; /* to avoid passing to all functions */
  43.  
  44. #define MAX_LZW_BITS    12      /* maximum LZW code size (4096 symbols) */
  45.  
  46. typedef INT16 code_int;         /* must hold -1 .. 2**MAX_LZW_BITS */
  47.  
  48. #define LZW_TABLE_SIZE  ((code_int) 1 << MAX_LZW_BITS)
  49.  
  50. #define HSIZE           5003    /* hash table size for 80% occupancy */
  51.  
  52. typedef int hash_int;           /* must hold -2*HSIZE..2*HSIZE */
  53.  
  54. static int n_bits;              /* current number of bits/code */
  55. static code_int maxcode;        /* maximum code, given n_bits */
  56. #define MAXCODE(n_bits) (((code_int) 1 << (n_bits)) - 1)
  57.  
  58. static int init_bits;           /* initial n_bits ... restored after clear */
  59.  
  60. static code_int ClearCode;      /* clear code (doesn't change) */
  61. static code_int EOFCode;        /* EOF code (ditto) */
  62.  
  63. static code_int free_code;      /* first not-yet-used symbol code */
  64.  
  65. /*
  66.  * The LZW hash table consists of three parallel arrays:
  67.  *   hash_code[i]       code of symbol in slot i, or 0 if empty slot
  68.  *   hash_prefix[i]     symbol's prefix code; undefined if empty slot
  69.  *   hash_suffix[i]     symbol's suffix character; undefined if empty slot
  70.  * where slot values (i) range from 0 to HSIZE-1.
  71.  *
  72.  * Algorithm:  use open addressing double hashing (no chaining) on the
  73.  * prefix code / suffix character combination.  We do a variant of Knuth's
  74.  * algorithm D (vol. 3, sec. 6.4) along with G. Knott's relatively-prime
  75.  * secondary probe.
  76.  *
  77.  * The hash tables are allocated from FAR heap space since they would use up
  78.  * rather a lot of the near data space in a PC.
  79.  */
  80.  
  81. static code_int FAR *hash_code; /* => hash table of symbol codes */
  82. static code_int FAR *hash_prefix; /* => hash table of prefix symbols */
  83. static UINT8 FAR *hash_suffix;  /* => hash table of suffix bytes */
  84.  
  85.  
  86. /*
  87.  * Routines to package compressed data bytes into GIF data blocks.
  88.  * A data block consists of a count byte (1..255) and that many data bytes.
  89.  */
  90.  
  91. static int bytesinpkt;          /* # of bytes in current packet */
  92. static char packetbuf[256];     /* workspace for accumulating packet */
  93.  
  94.  
  95. LOCAL void
  96. flush_packet (void)
  97. /* flush any accumulated data */
  98. {
  99.   if (bytesinpkt > 0) {         /* never write zero-length packet */
  100.     packetbuf[0] = bytesinpkt++;
  101.     if (fwrite(packetbuf, 1, bytesinpkt, dcinfo->output_file) != bytesinpkt)
  102.       ERREXIT(dcinfo->emethods, "Output file write error");
  103.     bytesinpkt = 0;
  104.   }
  105. }
  106.  
  107.  
  108. LOCAL void
  109. char_out (int c)
  110. /* Add a character to current packet; flush to disk if necessary */
  111. {
  112.   packetbuf[++bytesinpkt] = c;
  113.   if (bytesinpkt >= 255)
  114.     flush_packet();
  115. }
  116.  
  117.  
  118. /* Routine to convert variable-width codes into a byte stream */
  119.  
  120. static INT32 cur_accum;         /* holds bits not yet output */
  121. static int cur_bits;            /* # of bits in cur_accum */
  122.  
  123.  
  124. LOCAL void
  125. output (code_int code)
  126. /* Emit a code of n_bits bits */
  127. /* Uses cur_accum and cur_bits to reblock into 8-bit bytes */
  128. {
  129.   if (cur_bits > 0)
  130.     cur_accum |= ((INT32) code << cur_bits);
  131.   else
  132.     cur_accum = code;
  133.   cur_bits += n_bits;
  134.  
  135.   while (cur_bits >= 8) {
  136.     char_out((int) (cur_accum & 0xFF));
  137.     cur_accum >>= 8;
  138.     cur_bits -= 8;
  139.   }
  140.  
  141.   /*
  142.    * If the next entry is going to be too big for the code size,
  143.    * then increase it, if possible.  We do this here to ensure
  144.    * that it's done in sync with the decoder's codesize increases.
  145.    */
  146.   if (free_code > maxcode) {
  147.     n_bits++;
  148.     if (n_bits == MAX_LZW_BITS)
  149.       maxcode = LZW_TABLE_SIZE; /* free_code will never exceed this */
  150.     else
  151.       maxcode = MAXCODE(n_bits);
  152.   }
  153. }
  154.  
  155.  
  156. /* The LZW algorithm proper */
  157.  
  158. static code_int waiting_code;   /* symbol not yet output; may be extendable */
  159. static boolean first_byte;      /* if TRUE, waiting_code is not valid */
  160.  
  161.  
  162. LOCAL void
  163. clear_hash (void)
  164. /* Fill the hash table with empty entries */
  165. {
  166.   /* It's sufficient to zero hash_code[] */
  167.   jzero_far((void FAR *) hash_code, HSIZE * SIZEOF(code_int));
  168. }
  169.  
  170.  
  171. LOCAL void
  172. clear_block (void)
  173. /* Reset compressor and issue a Clear code */
  174. {
  175.   clear_hash();                 /* delete all the symbols */
  176.   free_code = ClearCode + 2;
  177.   output(ClearCode);            /* inform decoder */
  178.   n_bits = init_bits;           /* reset code size */
  179.   maxcode = MAXCODE(n_bits);
  180. }
  181.  
  182.  
  183. LOCAL void
  184. compress_init (int i_bits)
  185. /* Initialize LZW compressor */
  186. {
  187.   /* init all the static variables */
  188.   n_bits = init_bits = i_bits;
  189.   maxcode = MAXCODE(n_bits);
  190.   ClearCode = ((code_int) 1 << (init_bits - 1));
  191.   EOFCode = ClearCode + 1;
  192.   free_code = ClearCode + 2;
  193.   first_byte = TRUE;            /* no waiting symbol yet */
  194.   /* init output buffering vars */
  195.   bytesinpkt = 0;
  196.   cur_accum = 0;
  197.   cur_bits = 0;
  198.   /* clear hash table */
  199.   clear_hash();
  200.   /* GIF specifies an initial Clear code */
  201.   output(ClearCode);
  202. }
  203.  
  204.  
  205. LOCAL void
  206. compress_byte (int c)
  207. /* Accept and compress one 8-bit byte */
  208. {
  209.   register hash_int i;
  210.   register hash_int disp;
  211.  
  212.   if (first_byte) {             /* need to initialize waiting_code */
  213.     waiting_code = c;
  214.     first_byte = FALSE;
  215.     return;
  216.   }
  217.  
  218.   /* Probe hash table to see if a symbol exists for
  219.    * waiting_code followed by c.
  220.    * If so, replace waiting_code by that symbol and return.
  221.    */
  222.   i = ((hash_int) c << (MAX_LZW_BITS-8)) + waiting_code;
  223.   /* i is less than twice 2**MAX_LZW_BITS, therefore less than twice HSIZE */
  224.   if (i >= HSIZE)
  225.     i -= HSIZE;
  226.   
  227.   if (hash_code[i] != 0) {      /* is first probed slot empty? */
  228.     if (hash_prefix[i] == waiting_code && hash_suffix[i] == c) {
  229.       waiting_code = hash_code[i];
  230.       return;
  231.     }
  232.     if (i == 0)                 /* secondary hash (after G. Knott) */
  233.       disp = 1;
  234.     else
  235.       disp = HSIZE - i;
  236.     while (1) {
  237.       i -= disp;
  238.       if (i < 0)
  239.         i += HSIZE;
  240.       if (hash_code[i] == 0)
  241.         break;                  /* hit empty slot */
  242.       if (hash_prefix[i] == waiting_code && hash_suffix[i] == c) {
  243.         waiting_code = hash_code[i];
  244.         return;
  245.       }
  246.     }
  247.   }
  248.  
  249.   /* here when hashtable[i] is an empty slot; desired symbol not in table */
  250.   output(waiting_code);
  251.   if (free_code < LZW_TABLE_SIZE) {
  252.     hash_code[i] = free_code++; /* add symbol to hashtable */
  253.     hash_prefix[i] = waiting_code;
  254.     hash_suffix[i] = c;
  255.   } else
  256.     clear_block();
  257.   waiting_code = c;
  258. }
  259.  
  260.  
  261. LOCAL void
  262. compress_term (void)
  263. /* Clean up at end */
  264. {
  265.   /* Flush out the buffered code */
  266.   if (! first_byte)
  267.     output(waiting_code);
  268.   /* Send an EOF code */
  269.   output(EOFCode);
  270.   /* Flush the bit-packing buffer */
  271.   if (cur_bits > 0) {
  272.     char_out((int) (cur_accum & 0xFF));
  273.   }
  274.   /* Flush the packet buffer */
  275.   flush_packet();
  276. }
  277.  
  278.  
  279. /* GIF header construction */
  280.  
  281.  
  282. LOCAL void
  283. put_word (UINT16 w)
  284. /* Emit a 16-bit word, LSB first */
  285. {
  286.   putc(w & 0xFF, dcinfo->output_file);
  287.   putc((w >> 8) & 0xFF, dcinfo->output_file);
  288. }
  289.  
  290.  
  291. LOCAL void
  292. put_3bytes (int val)
  293. /* Emit 3 copies of same byte value --- handy subr for colormap construction */
  294. {
  295.   putc(val, dcinfo->output_file);
  296.   putc(val, dcinfo->output_file);
  297.   putc(val, dcinfo->output_file);
  298. }
  299.  
  300.  
  301. LOCAL void
  302. emit_header (int num_colors, JSAMPARRAY colormap)
  303. /* Output the GIF file header, including color map */
  304. /* If colormap==NULL, synthesize a gray-scale colormap */
  305. {
  306.   int BitsPerPixel, ColorMapSize, InitCodeSize, FlagByte;
  307.   int i;
  308.  
  309.   if (num_colors > 256)
  310.     ERREXIT(dcinfo->emethods, "GIF can only handle 256 colors");
  311.   /* Compute bits/pixel and related values */
  312.   if (num_colors <= 2)
  313.     BitsPerPixel = 1;
  314.   else if (num_colors <= 4)
  315.     BitsPerPixel = 2;
  316.   else if (num_colors <= 8)
  317.     BitsPerPixel = 3;
  318.   else if (num_colors <= 16)
  319.     BitsPerPixel = 4;
  320.   else if (num_colors <= 32)
  321.     BitsPerPixel = 5;
  322.   else if (num_colors <= 64)
  323.     BitsPerPixel = 6;
  324.   else if (num_colors <= 128)
  325.     BitsPerPixel = 7;
  326.   else
  327.     BitsPerPixel = 8;
  328.   ColorMapSize = 1 << BitsPerPixel;
  329.   if (BitsPerPixel <= 1)
  330.     InitCodeSize = 2;
  331.   else
  332.     InitCodeSize = BitsPerPixel;
  333.   /*
  334.    * Write the GIF header.
  335.    * Note that we generate a plain GIF87 header for maximum compatibility.
  336.    */
  337.   fwrite("GIF87a", 1, 6, dcinfo->output_file);
  338.   /* Write the Logical Screen Descriptor */
  339.   put_word((UINT16) dcinfo->image_width);
  340.   put_word((UINT16) dcinfo->image_height);
  341.   FlagByte = 0x80;              /* Yes, there is a global color table */
  342.   FlagByte |= (BitsPerPixel-1) << 4; /* color resolution */
  343.   FlagByte |= (BitsPerPixel-1); /* size of global color table */
  344.   putc(FlagByte, dcinfo->output_file);
  345.   putc(0, dcinfo->output_file); /* Background color index */
  346.   putc(0, dcinfo->output_file); /* Reserved in GIF87 (aspect ratio in GIF89) */
  347.   /* Write the Global Color Map */
  348.   for (i=0; i < ColorMapSize; i++) {
  349.     if (i < num_colors) {
  350.       if (colormap != NULL) {
  351.         if (dcinfo->out_color_space == CS_RGB) {
  352.           /* Normal case: RGB color map */
  353.           putc(GETJSAMPLE(colormap[0][i]), dcinfo->output_file);
  354.           putc(GETJSAMPLE(colormap[1][i]), dcinfo->output_file);
  355.           putc(GETJSAMPLE(colormap[2][i]), dcinfo->output_file);
  356.         } else {
  357.           /* Grayscale "color map": possible if quantizing grayscale image */
  358.           put_3bytes(GETJSAMPLE(colormap[0][i]));
  359.         }
  360.       } else {
  361.         /* Create a gray-scale map of num_colors values, range 0..255 */
  362.         put_3bytes((i * 255 + (num_colors-1)/2) / (num_colors-1));
  363.       }
  364.     } else {
  365.       /* fill out the map to a power of 2 */
  366.       put_3bytes(0);
  367.     }
  368.   }
  369.   /* Write image separator and Image Descriptor */
  370.   putc(',', dcinfo->output_file); /* separator */
  371.   put_word((UINT16) 0);         /* left/top offset */
  372.   put_word((UINT16) 0);
  373.   put_word((UINT16) dcinfo->image_width); /* image size */
  374.   put_word((UINT16) dcinfo->image_height);
  375.   /* flag byte: not interlaced, no local color map */
  376.   putc(0x00, dcinfo->output_file);
  377.   /* Write Initial Code Size byte */
  378.   putc(InitCodeSize, dcinfo->output_file);
  379.  
  380.   /* Initialize for LZW compression of image data */
  381.   compress_init(InitCodeSize+1);
  382. }
  383.  
  384.  
  385.  
  386. /*
  387.  * Initialize for GIF output.
  388.  */
  389.  
  390. METHODDEF void
  391. output_init (decompress_info_ptr cinfo)
  392. {
  393.   dcinfo = cinfo;               /* save for use by local routines */
  394.   if (cinfo->final_out_comps != 1) /* safety check */
  395.     ERREXIT(cinfo->emethods, "GIF output got confused");
  396.   /* Allocate space for hash table */
  397.   hash_code = (code_int FAR *) (*cinfo->emethods->alloc_medium)
  398.                                 (HSIZE * SIZEOF(code_int));
  399.   hash_prefix = (code_int FAR *) (*cinfo->emethods->alloc_medium)
  400.                                 (HSIZE * SIZEOF(code_int));
  401.   hash_suffix = (UINT8 FAR *) (*cinfo->emethods->alloc_medium)
  402.                                 (HSIZE * SIZEOF(UINT8));
  403.   /*
  404.    * If we aren't quantizing, put_color_map won't be called,
  405.    * so emit the header now.  This only happens with gray scale output.
  406.    * (If we are quantizing, wait for the color map to be provided.)
  407.    */
  408.   if (! cinfo->quantize_colors)
  409.     emit_header(256, (JSAMPARRAY) NULL);
  410. }
  411.  
  412.  
  413. /*
  414.  * Write the color map.
  415.  */
  416.  
  417. METHODDEF void
  418. put_color_map (decompress_info_ptr cinfo, int num_colors, JSAMPARRAY colormap)
  419. {
  420.   emit_header(num_colors, colormap);
  421. }
  422.  
  423.  
  424. /*
  425.  * Write some pixel data.
  426.  */
  427.  
  428. METHODDEF void
  429. put_pixel_rows (decompress_info_ptr cinfo, int num_rows,
  430.                 JSAMPIMAGE pixel_data)
  431. {
  432.   register JSAMPROW ptr;
  433.   register long col;
  434.   register long width = cinfo->image_width;
  435.   register int row;
  436.   
  437.   for (row = 0; row < num_rows; row++) {
  438.     ptr = pixel_data[0][row];
  439.     for (col = width; col > 0; col--) {
  440.       compress_byte(GETJSAMPLE(*ptr));
  441.       ptr++;
  442.     }
  443.   }
  444. }
  445.  
  446.  
  447. /*
  448.  * Finish up at the end of the file.
  449.  */
  450.  
  451. METHODDEF void
  452. output_term (decompress_info_ptr cinfo)
  453. {
  454.   /* Flush LZW mechanism */
  455.   compress_term();
  456.   /* Write a zero-length data block to end the series */
  457.   putc(0, cinfo->output_file);
  458.   /* Write the GIF terminator mark */
  459.   putc(';', cinfo->output_file);
  460.   /* Make sure we wrote the output file OK */
  461.   fflush(cinfo->output_file);
  462.   if (ferror(cinfo->output_file))
  463.     ERREXIT(cinfo->emethods, "Output file write error");
  464.   /* Free space */
  465.   (*cinfo->emethods->free_medium) ((void FAR *) hash_code);
  466.   (*cinfo->emethods->free_medium) ((void FAR *) hash_prefix);
  467.   (*cinfo->emethods->free_medium) ((void FAR *) hash_suffix);
  468. }
  469.  
  470.  
  471. /*
  472.  * The method selection routine for GIF format output.
  473.  * This should be called from d_ui_method_selection if GIF output is wanted.
  474.  */
  475.  
  476. GLOBAL void
  477. jselwgif (decompress_info_ptr cinfo)
  478. {
  479.   cinfo->methods->output_init = output_init;
  480.   cinfo->methods->put_color_map = put_color_map;
  481.   cinfo->methods->put_pixel_rows = put_pixel_rows;
  482.   cinfo->methods->output_term = output_term;
  483.  
  484.   if (cinfo->out_color_space != CS_GRAYSCALE &&
  485.       cinfo->out_color_space != CS_RGB)
  486.     ERREXIT(cinfo->emethods, "GIF output must be grayscale or RGB");
  487.  
  488.   /* Force quantization if color or if > 8 bits input */
  489.   if (cinfo->out_color_space == CS_RGB || cinfo->data_precision > 8) {
  490.     /* Force quantization to at most 256 colors */
  491.     cinfo->quantize_colors = TRUE;
  492.     if (cinfo->desired_number_of_colors > 256)
  493.       cinfo->desired_number_of_colors = 256;
  494.   }
  495. }
  496.  
  497. #endif /* GIF_SUPPORTED */
  498.